package daily.oct;

import java.util.*;

public class lc1488 {

    public int[] avoidFlood(int[] rains) {
        int n = rains.length;
        int[] res = new int[n];
        Arrays.fill(res, 1); // 默认抽干任意一个湖泊
        
        Map<Integer, Integer> lastRain = new HashMap<>(); // 记录湖泊上次下雨的日期
        TreeSet<Integer> dryDays = new TreeSet<>(); // 记录所有晴天的位置
        
        for (int i = 0; i < n; i++) {
            if (rains[i] == 0) {
                // 记录晴天位置
                dryDays.add(i);
            } else {
                // 下雨天，标记为-1
                res[i] = -1;
                int lake = rains[i];
                
                if (lastRain.containsKey(lake)) {
                    // 这个湖泊之前下过雨，需要找到之后的晴天来抽干它
                    Integer dryDay = dryDays.higher(lastRain.get(lake));
                    if (dryDay == null) {
                        // 没有合适的晴天来抽干，会发生洪水
                        return new int[0];
                    }
                    // 在这个晴天抽干湖泊
                    res[dryDay] = lake;
                    dryDays.remove(dryDay);
                }
                // 更新湖泊最后下雨的日期
                lastRain.put(lake, i);
            }
        }
        
        return res;
    }
    
    public static void main(String[] args) {
        lc1488 lc = new lc1488();
        int[] rains = {1, 2, 0, 0, 2, 1};
        int[] res = lc.avoidFlood(rains);
        for (int r : res) {
            System.out.print(r + " ");
        }
        // 输出: -1 -1 2 1 -1 -1
    }
}